package hot

/**
原题链接:
https://leetcode.cn/problems/evaluate-division/

Hot 399.除法求值
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，
其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。
每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，
请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。
如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

返回所有问题的答案. 如果存在某个无法确定的答案, 则用-1.0 替代这个答案
如果问题中出现了给定的已知条件中没有出现的字符串, 也需要用 -1.0 替代这个答案
注意: 输入总是有效的. 你可以假设除法运算中不会出现除数为0的情况, 且不存在任何矛盾的结果
注意: 未在等式列表中出现的变量是未定义的, 因此无法确定它们的答案.

示例 1：
输入：
equations = [["a","b"],["b","c"]],
values = [2.0,3.0],
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0

示例 2：
输入：
equations = [["a","b"],["b","c"],["bc","cd"]],
values = [1.5,2.5,5.0],
queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]


思路:
并查集(Disjoin-set)简介
并查集(不相交集合) 用于处理动态连通性问题, 最典型的应用是求解[最小生成树]的Kruskal算法
并查集支持[查询(find)],[合并(union)]两个操作
并查集只会打两个节点是不是在一个连通分量中(也就是所谓的连通性问题), 并不回答路径问题
如果一个问题具有传递性质, 可以考虑用并查集

并查集最常见的一种设计思想是: 把同在一个连通分量中的节点组织成一个树形结构(代表元法)
所谓两个节点在一个集合中,等价于,它们的根节点相同
所谓合并两个集合, 就是把其中一棵树的根节点的父亲节点, 指向另一颗树的根节点

并查集使用[路径压缩]与[按秩合并]解决树的高度增加带来的[查询]性能的消耗问题

*/

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	id := map[string]int{}
	for _, v := range equations {
		if _, ok := id[v[0]]; !ok { //不在id中
			id[v[0]] = len(id) //id就是当前的map长度
		}
		if _, ok := id[v[1]]; !ok {
			id[v[1]] = len(id)
		}
	}
	father := make([]int, len(id))     //记录每个字符串的father，即除数
	weight := make([]float64, len(id)) //记录与father当除数时的商
	for i := 0; i < len(father); i++ {
		father[i] = i //初始化father为自己
		weight[i] = 1 //因为father为自己故商为1
	}
	var find func(int) int
	find = func(x int) int {
		if father[x] != x {
			fa := find(father[x])
			weight[x] *= weight[father[x]] //寻找father本身的过程就是不断找除数的过程，所以x除以新father的商需要乘上老father除以新father 的商
			father[x] = fa
		}
		return father[x] //x==father[x]
	}
	merge := func(left, right int, val float64) {
		leftFather, rightFather := find(left), find(right)
		weight[leftFather] = val * weight[right] / weight[left] //left老father除以新father的商
		father[leftFather] = rightFather                        //令left老father的新father为right的father
	}
	for k, v := range equations {
		merge(id[v[0]], id[v[1]], values[k])
	}
	res := make([]float64, len(queries))
	for i, query := range queries {
		left, hasLeft := id[query[0]]
		right, hasRight := id[query[1]]
		if hasLeft && hasRight && find(left) == find(right) {
			res[i] = weight[left] / weight[right]
		} else {
			res[i] = -1
		}
	}
	return res
}
